#include<iostream>

using namespace std;


//双指针算法;
//1.快乐数:
class Solution 
{
public:

    int bitset(int n)
    {
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) 
    {
        int slow = n, fast = bitset(n);
        while(slow != fast)
        {
            slow = bitset(slow);
            fast = bitset(bitset(fast));
        }
        return slow == 1;
    }
};

// 2. 盛水最多的容器;
#include<vector>
class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size()-1;
        //int ret = INT_MIN;
        while(left < right)
        {
            int v = (right-left) * min(height[left], height[right]);
            //ret = max(ret, v);

            if(height[left] < height[right])
                left++;
            else 
                right--;
        }
        //return ret;
    }
};

// 3. 有效三角形的个数;
#include<algorithm>
class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int ret = 0;
        for(int i = nums.size()-1; i >= 2; i--)
        {
            int left = 0, right = i-1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};


// 4.查找总价格为目标值的商品;
class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        vector<int> ret;
        int left = 0, right = price.size()-1;
        while(left < right)
        {
            int sum = price[left] + price[right];
            if(sum > target)
            {
                right--;
            }
            else if(sum < target)
            {
                left++;
            }
            else
            {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};

// 5. 三数之和
class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ret;
        for(int i = 0; i < nums.size(); )
        {
            int left = i + 1, right = nums.size()-1;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                int target = -nums[i];
                if(sum < target)
                {
                    left++;
                }  
                else if(sum  > target)
                {
                    right--;
                }
                else
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    
                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
            }
            i++;
            while(i < nums.size() && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};


//  6. 四数之和;
class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); )
        {
            for(int j = i + 1; j < nums.size(); )
            {
                int left = j+1, right = nums.size()-1;
                long long temp = (long long)target - (long long)nums[i] - (long long)nums[j];
                while(left < right)
                {
                    int sum = (long long)nums[left] + (long long)nums[right];
                    if(sum < temp)
                    {
                        left++;
                    }
                    else if(sum > temp)
                    {
                        right--;
                    }
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left-1])
                            left++;
                        
                        while(left < right && nums[right] == nums[right+1])
                            right--;
                    }
                }
                j++;
                while(j < nums.size() && nums[j] == nums[j-1])
                    j++;
            }
            i++;
            while(i < nums.size() && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};


//滑动窗口:
//1.长度最小的子数组;
class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        if(nums.size() == 0)
            return 0;
        int left = 0, right = 0;
        int sum = 0, len = INT_MAX;
        while(right < nums.size())
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right-left+1);
                sum -= nums[left++];
            }
            right++;
        }
        return len == INT_MAX ? 0 : len;
    }
};

// 2. 无重复字符的最长字串;
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[128] = {0};
        int left = 0, right = 0;
        int len = INT_MIN;
        while(right < s.size())
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1)
            {
                hash[s[left++]]--;
            }
            len = max(len, right-left+1);
            right++;
        }
        return len == INT_MIN ? 0 : len;
    }
};

// 3.最大连续1的个数;
class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int len = INT_MIN;
        int left, right;
        int count = 0;
        for(left = 0, right = 0; right < nums.size(); right++)
        {
            if(nums[right] == 0)
                count++;

            while(count > k)
            {
                if(nums[left++] == 0)
                    count--;
            }

            len = max(len, right-left+1);
        }
        return len == INT_MIN ? 0 : len;
    }
};

// 4.将x减到0最小操作数


